#pragma once
#ifndef _SOLVER_H
#define _SOLVER_H


#include <stack>

#include "move.h"
#include "stackrecord.h"
#include "solution.h"
#include "Instance.h"

class Solver
{

public:

	//////////////////////////////////////////////////////////////////////////
	Solver(Instance &_in): instance(_in)
	{
		solutionLayout = StackRecord::boardLayout_t(instance.n() * instance.n());
	}
	
	//////////////////////////////////////////////////////////////////////////
	virtual Solution solve()
	{
		createSolLay();
		StackRecord::boardLayout_t start = createLayout(instance);
		stateCounter = 0;

		openNodes.push(StackRecord(start)); //s prazdnou historii
		while (!openNodes.empty())
		{	
			//utils::dumpStack(openNodes, std::cout, stateCounter);
			processTopSolution();
			//Protoze prave ted po zpracovani reseni muze byt zasobnik vyprazdnen,
			//musim ho otestovat pred expanzi, jinak by mohlo dojit k chybe.
			if(openNodes.empty()) break;
			expandTop();
		}

		std::cout << "States discovered: " << this->stateCounter << std::endl;

		//return Solution
		return tempBest;
	}
	
	//////////////////////////////////////////////////////////////////////////
	virtual ~Solver()
	{
	}

private:
	Instance instance;
	std::stack<StackRecord> openNodes;
	StackRecord::boardLayout_t solutionLayout;
	Solution tempBest;
	size_t stateCounter;

	//////////////////////////////////////////////////////////////////////////
	//Vytvori rozlozeni sachovnice odpovidajici hledanemu reseni.
	void createSolLay()
	{
		unsigned cnt = instance.k();
		unsigned y = 0, x = 0; //zacnu nahore vlevo
		unsigned zarazka = instance.n();
		while (cnt > 0)
		{
			unsigned index = utils::coordsToIndex(x,y,instance.n());
			//solutionLayout[index]=1;
			solutionLayout.setAt(index,true);
			x++;
			if (x>=zarazka)
			{
				x = 0; //zpet na zacatek radku
				y++; //po radcich dolu
				zarazka--;
			}
			cnt--;
		}
	}
	
	//////////////////////////////////////////////////////////////////////////
	void processTopSolution()
	{
		if(isTopSolution())
		{ //na vrcholu zasobniku je reseni!
			StackRecord top = openNodes.top();
			openNodes.pop(); //z reseni uz nebude lepsi.. leda bychom meli zaporne penalizace (coz nemame)
			if (tempBest.penaltySum > top.totalPenalty)
			{ //nasli jsme lepsi reseni!
				std::cout << "Velikost zasobniku: "<< openNodes.size() << "\n";
				std::cout << "Pocet prohledanych stavu: "<< this->stateCounter << "\n";
				std::cout << "SOLUTION:\n" << top << std::endl;
				tempBest = Solution(top.movesHistory, top.totalPenalty);
			}
		}
		//pokud neni reseni, nic se nestane.
	}

	//////////////////////////////////////////////////////////////////////////
	bool isTopSolution()
	{
		return openNodes.top().boardLayout == solutionLayout;
	}

	//////////////////////////////////////////////////////////////////////////
	void expandTop()
	{
		StackRecord actual = openNodes.top();
		//std::cerr << actual << std::endl;
		openNodes.pop();
		this->stateCounter++;
		//max hloubka:
		if (actual.depth == instance.q())
		{
			return;
		}
		//uchovam si souradnice na vychozi pozici posledne tazeneho kone:
		utils::coords_t * origCp = 0;
		if (!actual.movesHistory.empty()) //pozor pri prvnim tahu, zadna historie..
		{
			origCp = &(actual.movesHistory.back().origCoords);
		}
		//Generovani vsech tahu:
		for (unsigned i = 0; i<actual.boardLayout.size(); ++i)
		{
			if (!actual.boardLayout[i])
			{
				continue;
			}
			for (unsigned j = 1; j<=8; ++j)
			{
				Move m(utils::indexToCoords(i,instance.n()), (Direction) j);
				if (origCp && m.targetCoords == *origCp)
				{
					continue;
				}
				StackRecord::boardLayout_t newL = move(actual.boardLayout, m);
				if (newL == actual.boardLayout)
				{	//Pokud je tah neplatny, vratilo mi to nezmenenou konfiguraci
					continue; 
				}
				unsigned pen = instance.getPenalty(m.targetCoords);
				if (actual.totalPenalty+pen >= tempBest.penaltySum)
				{ //orezani podle penalizace, pred ulozenim na zasobnik
					stateCounter++;
					continue;
				}
				openNodes.push(StackRecord(newL,actual,m,pen));
			}
		}

	} //end expandTop

	//////////////////////////////////////////////////////////////////////////
	// Funkce, ktera aplikuje samotny tah na danou desku.
	// Nezda se to jako uplne dobry navrh (objektove), ale funguje..
	//
	// returns new layout or the SAME layout (as on input), if the move would be invalid.
	StackRecord::boardLayout_t move(const StackRecord::boardLayout_t &_inLay, const Move& _m)
	{
		unsigned new_index;
		if(	_m.targetCoords.first>=instance.n() || //kontrola souradnic
			_m.targetCoords.second>=instance.n() ||
			_inLay[(new_index = utils::coordsToIndex(_m.targetCoords, instance.n()))] //test cilove pozice, jestli je volna
			)
		{
			return _inLay; //v pripade ze tento tah neni platny, vratim puvodni rozlozeni
		}
		StackRecord::boardLayout_t new_lay = _inLay;
		new_lay.setAt(utils::coordsToIndex(_m.origCoords, instance.n()), false);
		new_lay.setAt(new_index, true);

		return new_lay;
	} //end move

	//////////////////////////////////////////////////////////////////////////
	//Metoda pro vytvoreni bitmapy sachovnice pro dane zadani.
	static StackRecord::boardLayout_t createLayout(Instance &_inst)
	{
		StackRecord::boardLayout_t lay(_inst.n() * _inst.n()); //velikost n*n !!
		for (unsigned i = 0; i < _inst.getHorses().size(); ++i)
		{
			unsigned x = _inst.getHorses()[i].x;
			unsigned y = _inst.getHorses()[i].y;
			unsigned index = utils::coordsToIndex( x, y, _inst.n());
			lay.setAt(index, true);
		}
		return lay;
	}
};


#endif
